/*
要求：判断一个字符串是否可以通配符匹配另一个字符串，？代替一个字符、* 代替多个字符
策略：动态规划
 */
public class IsMatch {
}
class IsMathSolution{
    boolean isMath(String s,String p){
        char[] chas = s.toCharArray();
        char[] chap = p.toCharArray();
        int m = chas.length;
        int n = chap.length;
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i=1;i<=n;i++){
            if(chap[i-1]=='*')
                dp[0][i] = true;
            else
                break;
        }
        //递推关系式
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(chap[j-1]=='*')
                    dp[i][j] = dp[i][j-1]|dp[i-1][j];//‘*’可以充当空字符或匹配当前chas[i-1]字符
                else if(chap[j-1]==chas[i-1]||chap[j]=='?')
                    dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //暴力回溯
    boolean dfs(char[] chas,char[] chap,int is,int ip){
        if(ip==chap.length&&is==chas.length)
            return true;
        if(ip==chap.length||(is==chas.length&&chap[ip]!='*'))
            return false;
        if(chap[ip]=='*'&&is!=chas.length)return dfs(chas,chap,is+1,ip)|dfs(chas,chap,is+1,ip+1)|dfs(chas,chap,is,ip+1);
        else if(chap[ip]=='*')return dfs(chas,chap,is,ip+1);
        else if(chap[ip]=='?')return dfs(chas,chap,is+1,ip+1);
        else if(chap[ip]!=chas[is])return false;
        else return dfs(chas,chap,is+1,ip+1);
    }
}